The present invention is directed to graphic imaging devices, such as printers and display monitors, and more particularly to the manner in which image data is stored in such devices during the process of generating an image.
In a computer-based imaging system, data which describes an image is generated in a host computer, for example using a desktop publishing program, and then forwarded to an image generating device where it is converted into a format that can be used by the device. In an exemplary system, the image data from the host computer might be in the format of a high-level page description language (PDL). One example of a well-known PDL is PostScript. In the host computer, graphic commands from the desktop publishing program, or other suitable application program, are converted into PDL commands. These commands are sent to the printer which interprets them and determines which types of graphics operations are to be performed, such as draw a rectangle or a particular character of text. The interpretation process typically also determines associated graphic state arguments that apply to each object, such as color, font, size, and the like. This information is then converted into pixel display values which are stored in a frame buffer to represent the shapes and colors of the objects. The values in the frame buffer are used to control the operation of the active elements in a print engine, such as a laser diode in a laser printer or a print head in an inkjet printer, to form the image. The process of converting the high-level PDL commands into the frame buffer display values is known as rendering.
To increase the overall rate at which printing is carried out, particularly for complex documents containing different types of objects, the various steps of the rendering process might be pipelined. At one or more stages of the process, the image data is converted to an intermediate form which can be utilized more efficiently by the next stage. For example, in one well-known type of operation relating to laser printers, high-level graphics operations are determined from the PDL data, and stored in a display list from which they are provided to the stage which generates the individual pixel display values.
The amount of information to be stored in an intermediate form is a significant consideration for purposes of efficient memory allocation in these types of applications. More particularly, each entry in the display list represents a shape or a graphics state command, e.g., color, to be applied to subsequent entries. In addition to this image data, each entry has some associated overhead information which is stored along with it. This overhead information might comprise a header which describes the type of entry, and a pointer or other reference to the next entry on the list. To the extent possible, it is desirable to minimize the amount of information to be stored.
In other types of imaging systems, lower level commands are transmitted between a control device, e.g., a computer, and an image forming device. Bit-maps, for example, involve transmitting information relating to each pixel to be imaged. In these types of systems, it is desirable to minimize the amount of information to be transmitted.
To determine an appropriate amount of data to be stored or transmitted, it is useful to consider how rendering is performed. In the world of raster graphics rendering, it is common to approximate curves and circular arcs using straight lines. Conventional raster graphics rendering techniques involve slicing such a straight-line approximated complex object into simpler representations such as lines, rectangles or trapezoids. Each line, rectangle or trapezoid is then rendered sequentially, for example from top to bottom of the complex object.
An example of raster graphics rendering using linear object slices is illustrated in FIG. 1. Therein an ellipse is rendered by sequentially drawing of said linear object slices in the form of raster lines, for example from the top of the ellipse to the bottom of the ellipse. Two coordinates are used to define each raster line; each line is to be sequentially rendered. In the example of FIG. 1, the two lines shown have coordinates XL1, XR1 and XL2, XR2, respectively. For each line that is to be rendered to create the ellipse of FIG. 1, the two parameters used to uniquely define the line are transmitted or stored depending upon the type of imaging system under consideration. For example, a PDL interpreter might receive a high level command to draw the ellipse of FIG. 1 and would then store each set of line coordinates in a display list.
Suppose that, instead of using linear object slices, a raster graphic subsystem used rectangles to render more complex objects. This type of rendering is illustrated in FIG. 2. In addition to the end points of the rectangle, the raster graphics subsystem also needs to know the height H of each rectangle. According to conventional techniques, for each rectangle that is to be rendered on a display, three parameters are transmitted to, or stored in intermediate form in, the raster graphics subsystem. In the example of FIG. 2, these three parameters are, for the middle rectangle, denoted as XL1, XR1 and H.
A third example is provided in FIG. 3. Therein, the elliptical object is rendered using a series of trapezoids as object slices. Each trapezoid is defined by an upper, lefthand coordinate, e.g., XL1, an upper, righthand coordinate, e.g., XR1, and a height H. Along each side of the trapezoid, there are also parameters which describe the change in gradient (i.e., slope) of the trapezoid as it traverses downwardly in the vertical direction. These parameters are denoted DXL and DXR for the left and right sides, respectively, of the middle trapezoid illustrated in FIG. 3.
In conventional rendering devices one slice of an object, e.g., a line, a rectangle or a trapezoid, is rendered at a time. Going from one slice to the next adjacent slice, all of the parameters that describe the location at which the next line, rectangle or trapezoid is to be rendered, are retransmitted, or stored in an intermediate form such as a display list, before further rendering can take place. For example, the parameters XL1, XR1, H, DXL and DXR would conventionally be retransmitted or stored for each trapezoidal object slice. However, as recognized by Applicants, each of these parameters does not always change from object slice to object slice. In fact, depending upon the geometry of the complex object being rendered, redundant information of object slice parameters is frequently transmitted or stored using these conventional rendering techniques. Thus, conventional rendering techniques which update graphical object slice parameters by transmitting all of the parameter information for each object slice between, for example, a host computer and a graphics rendering subsystem, create unnecessary overhead in the data transmission which hinders the performance of these conventional devices. Similarly, those conventional systems which convert all of the parameters for every object slice into some intermediate form, e.g., a display list, and store that information are inefficient and wasteful of system memory.